#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;

//class Solution {
//public:
//    bool canJump(vector<int>& nums) {
//        int jump = nums[0];
//        for (int i = 1; i < nums.size(); i++)
//        {
//            if (jump == 0)
//                return false;
//
//            jump--;
//            jump = max(jump, nums[i]);
//        }
//
//        return true;
//    }
//};
//
//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        int ret = 0;
//        int buy = prices[0];
//        for (int i = 1; i < prices.size(); i++)
//        {
//            if (prices[i] > buy)
//            {
//                ret = max(prices[i] - buy, ret);
//            }
//            else
//                buy = prices[i];
//        }
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int jump(vector<int>& nums) {
//        int maxPos = 0, n = nums.size(), end = 0, step = 0;
//        for (int i = 0; i < n - 1; ++i) {
//            if (maxPos >= i) {
//                maxPos = max(maxPos, i + nums[i]);
//                if (i == end) {
//                    end = maxPos;
//                    ++step;
//                }
//            }
//        }
//        return step;
//    }
//};

//class Solution {
//public:
//    vector<int> partitionLabels(string s) {
//        unordered_map<char, int> hash;
//        for (int i = 0; i < s.size(); i++)
//        {
//            hash[s[i]] = i;
//        }
//
//        vector<int> ret;
//
//        for (int start = 0, cur = 0, end = 0; cur < s.size(); cur++)
//        {
//            end = max(hash[s[cur]], end);
//            if (end == cur)
//            {
//                ret.push_back(end - start + 1);
//                start = end + 1;
//            }
//        }
//
//        return ret;
//    }
//};

//class Solution {
//public:
//
//    class Cmp
//    {
//    public:
//        bool operator()(const pair<int, int>& p1, const pair<int, int>& p2)
//        {
//            return p1.first > p2.first;
//        }
//    };
//
//    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
//    {
//        // priority_queue<pair<int, int>, Cmp> pq;
//        for (int i = 0; i < gas.size(); i++)
//        {
//            gas[i] -= cost[i];
//            // if(gas[i] >= 0)
//            //     pq.push({gas[i], i});
//        }
//
//        int count = 0;
//        for (int i = 0; i < gas.size(); i++)
//        {
//            count += gas[i];
//        }
//        if (count < 0) return -1;
//
//
//        // while(!pq.empty())
//        // {
//        //     pair<int, int> top = pq.top();
//        //     pq.pop();
//
//        //     int count = top.first, pos = (top.second + 1) % gas.size();
//        //     while(pos != i && count >= 0)
//        //     {
//        //         count += gas[pos];
//        //         pos = (pos + 1) % gas.size();
//        //     }
//
//        //     if(count >= 0) return i;
//        // }
//
//        int end = 0, pos = (end + 1) % gas.size(), cur_gas = gas[0];
//        while (end != pos)
//        {
//            if (cur_gas < 0)
//            {
//                end = pos;
//                cur_gas = gas[end];
//                pos = (end + 1) % gas.size();
//            }
//            else
//            {
//                cur_gas += gas[pos];
//                pos = (pos + 1) % gas.size();
//            }
//
//        }
//
//        return pos;
//    }
//};

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)
    {
        priority_queue<int> horizontal, vertical;
        for (auto e : horizontalCut)
        {
            horizontal.push(e);
        }
        for (auto e : verticalCut)
        {
            vertical.push(e);
        }
        int row = 1, col = 1;
        int ret = 0;
        while (!horizontal.empty() && !vertical.empty())
        {
            int h = horizontal.top(), v = vertical.top();
            if (h > v)
            {
                ret += h * col;
                horizontal.pop();
                row++;
            }
            else if (h < v)
            {
                ret += v * row;
                vertical.pop();
                col++;
            }
            else
            {
                if (row > col)
                {
                    ret += h * col;
                    horizontal.pop();
                    row++;
                }
                else
                {
                    ret += v * row;
                    vertical.pop();
                    col++;
                }
            }
        }

        while (!horizontal.empty())
        {
            int h = horizontal.top();
            ret += h * col;
            horizontal.pop();
            row++;
        }

        while (!vertical.empty())
        {
            int v = vertical.top();
            ret += v * row;
            vertical.pop();
            col++;
        }

        return ret;
    }
};

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int m = g.size(), n = s.size();
        int count = 0;
        for (int i = 0, j = 0; i < m && j < n; i++, j++) {
            while (j < n && g[i] > s[j]) {
                j++;
            }
            if (j < n) {
                count++;
            }
        }
        return count;
    }
};

class Solution {
public:
    int jump(vector<int>& nums)
    {
        int ret = 0;
        for (int i = 0; i < nums.size();)
        {
            if (i >= nums.size() - 1)
                break;

            int index = -1, num = -1;
            if (i + nums[i] >= nums.size() - 1)
            {
                ret++;
                break;
            }
            else
            {
                for (int j = i + 1; j < nums.size() && j <= i + nums[i]; j++)
                {
                    cout << j << " : " << j - i + nums[j] << " " << num << endl;
                    if (j - i + nums[j] >= num)
                    {
                        num = j - i + nums[j];
                        index = j;
                    }
                }

                cout << index << endl;
                i = index;
                ret++;
            }
        }

        return ret;
    }
};


class Solution {
public:
    bool checkPalindrome(const string& s, int low, int high) {
        for (int i = low, j = high; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

    bool validPalindrome(string s) {
        int low = 0, high = s.size() - 1;
        while (low < high) {
            char c1 = s[low], c2 = s[high];
            if (c1 == c2) {
                ++low;
                --high;
            }
            else {
                return checkPalindrome(s, low, high - 1) || checkPalindrome(s, low + 1, high);
            }
        }
        return true;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums)
    {
        int sum = nums[0];
        int low = nums[0] > 0 ? 0 : nums[0], ret = nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            sum += nums[i];
            ret = max(ret, sum - low);
            low = min(low, sum);
        }

        return ret;
    }
};

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](const int& x, const int& y) {
            return to_string(x) + to_string(y) > to_string(y) + to_string(x);
            });
        if (nums[0] == 0) {
            return "0";
        }
        string ret;
        for (int& x : nums) {
            ret += to_string(x);
        }
        return ret;
    }
};


int main()
{
    //Solution().partitionLabels("ababcbacadefegdehijhklij");
	return 0;
}

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums)
    {
        int r = -1, high = nums[0];
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] >= high)
            {
                high = nums[i];
            }
            else
            {
                r = i;
            }
        }

        int l = -1, low = nums[nums.size() - 1];
        for (int i = nums.size() - 2; i >= 0; i--)
        {
            if (nums[i] <= low)
            {
                low = nums[i];
            }
            else
            {
                l = i;
            }
        }

        if (r == -1 || l == -1)
        {
            return 0;
        }

        return r - l + 1;
    }
};